package ARBOL_BINARIO;
import javax.swing.JOptionPane;
import java.awt.*;
/**
 *
 * @author Richar Guaya...
 */
public class ArbolBinario {
    int nivel=1;
    static Nodo nodoRaiz;
    static int tiempo=0;
    //static Nodo refAnterior;
    
    public ArbolBinario(int x, Nodo nodoAnt) {
        nodoRaiz = new Nodo(x, nodoAnt, 1, 1);
    }
    public ArbolBinario(){
    }
    
    void Insertar(Nodo elem, int x, int nivel, int col) {
        tiempo++;
        int dir = 0;
        Nodo pNuevo = null;
        Nodo enlace = null;
        if (x < elem.informacion) {
            enlace = elem.refIzq;
            dir = 1;
        }
        if (x > elem.informacion) {
             enlace = elem.refDer;
            dir = 2;
        }
        
        if (enlace == null) {
            pNuevo = new Nodo(x, elem, nivel, col); 

            if (dir == 1){
               elem.refIzq = pNuevo;
               col=(elem.col*2)-1;
            }
            if (dir == 2){
               elem.refDer = pNuevo;
               col=elem.col*2;
            }
            pNuevo.col=col; //se modifica la posicion de la columna que estuvo en cero por defecto;
            pNuevo.nivel=elem.nivel*2;;
            nivel=1;
        }
        else {
            if (x < elem.informacion)
                Insertar(elem.refIzq, x, nivel, col); 
            if (x > elem.informacion)
                Insertar(elem.refDer, x, nivel, col); 
        }      
    }
    
    Nodo busquedaBinaria(Nodo raiz, int dato){
        boolean encontrado = false;
        while(!encontrado && raiz!=null){
            if(dato==raiz.informacion)
                encontrado=true;
            else if(dato<raiz.informacion)
                raiz=raiz.refIzq;
            else
                raiz=raiz.refDer;
        }
        return raiz;
    }
    
  
    void Eliminar (Nodo r, int x, Nodo refAnt) {
	if ( r == null )
            JOptionPane.showMessageDialog(null,"No se encuentra el nodo especificado");
	else {
            if ( x < r.informacion )
                Eliminar( r.refIzq, x, r );
            if ( x > r.informacion )
                Eliminar( r.refDer, x, r ); 
            if ( x == r.informacion ) {
               if ( r.refIzq == null ) {
                   if (refAnt.refIzq == r){
                       refAnt.refIzq = r.refDer;
                       r.refDer.nodoAnt=refAnt;
                       if(r.refIzq!=null)
                          r.refIzq.nodoAnt=refAnt;//por el nodo que se elimina los subsiguientes, pierden su referencia al nodo anterior
                       r.refDer.nodoAnt=r.nodoAnt;   
                   }
                   if (refAnt.refDer == r){
                       refAnt.refDer = r.refDer;
                       if(r.refDer!=null)
                          r.refDer.nodoAnt=refAnt;//por el nodo que se elimina los subsiguientes, pierden su referencia al nodo anterior
                       r.refIzq.nodoAnt=r.nodoAnt;   
                   }
                   PostOrden(r);
               }else if ( r.refDer == null ) {
                   if (refAnt.refIzq == r){
                       refAnt.refIzq = r.refIzq;
                       r.refIzq.nodoAnt=refAnt;
                   }
                   if (refAnt.refDer == r){
                       refAnt.refDer = r.refIzq;
                       r.refIzq.nodoAnt=refAnt;
                   }
                   PostOrden(r);
               }else{
                   this.Reemplazar(r);
                   if(r==nodoRaiz)
                       PostOrden(r);
               }
            }
        }   
    }
    
    void PostOrden(Nodo nodo) {
       if (nodo != null) {
           PostOrden(nodo.refIzq);
           PostOrden(nodo.refDer);  
           if(nodo.nodoAnt.informacion==nodoRaiz.informacion){
              if(nodo.refDer!=null)
                  nodo.refDer.nodoAnt=nodo.nodoAnt;
              if(nodo.refIzq!=null)
                  nodo.refIzq.nodoAnt=nodo.nodoAnt;
           }
           if(nodo.refIzq!=null && nodo!=nodoRaiz){
              nodo.refIzq.nivel=nodo.nivel;   
              nodo.refIzq.col=nodo.col;
              nodo.refIzq.nodoAnt=nodo;         
              if(nodo.refDer!=null){
                 nodo.refDer.nivel=nodo.nivel;
                 nodo.refDer.col=nodo.col+1;
                 nodo.refDer.nodoAnt=nodo;
              }
           }
           else if(nodo.refDer!=null && nodo!=nodoRaiz){
              nodo.refDer.nivel=nodo.nivel;
              nodo.refDer.col=nodo.col;
              nodo.refDer.nodoAnt=nodo;
              if(nodo.refIzq!=null){
                 nodo.refIzq.nivel=nodo.nivel;
                 nodo.refIzq.col=nodo.col+1;
                 nodo.refIzq.nodoAnt=nodo;
              }
           }
       }
    }
    void Reemplazar(Nodo act) {
        Nodo a;
	Nodo resp = null;

	a = act.refIzq;
	if (a.refDer == null) 
	{
            act.informacion = a.informacion;
            act.refIzq = a.refIzq;
	}
	else {
            while ( a.refDer != null )
            {
                resp = a;
                a = a.refDer;
            }
            act.informacion = a.informacion;
            resp.refDer = a.refIzq;
	}
    }
}
